10941. TF problem

Given a string of length n, consisting of a block of T characters followed by a block of F characters, find the index of the last T character or print -1 if T is not present in the string.

Character indexing in the string starts from 0.

Input. One string containing no more than 10⁶ characters.

Output. Print the index of the last T character. If the string does not contain T, print -1.

Sample input	Sample output
TTTTFF	3

SOLUTION

binary search

Algorithm analysis

If the first character of the string is F, print -1. Otherwise, find the index of the last T character using binary search.

Algorithm implementation

The BinSearch function performs a binary search and returns the index of the last T character.

int BinSearch(string& s)

{

int l = 0, r = s.size();

while (l < r)

{

int mid = (l + r) / 2;

if (s[mid] == 'T') l = mid + 1;

else r = mid;

}

return l - 1;

}

The main part of the program. Read the input string s.

cin >> s;

If the first character of the string is F, print -1.

if (s[0] == 'F') cout << -1 << endl;

Print the answer.

else cout << BinSearch(s) << endl;

Java implementation

import java.util.*;

public class Main

{

static int BinSearch(String s)

{

int l = 0, r = s.length();

while (l < r)

{

int mid = (l + r) / 2;

if (s.charAt(mid) == 'T') l = mid + 1;

else r = mid;

}

return l - 1;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

String s = con.next();

if (s.charAt(0) == 'F') System.out.println(-1);

else System.out.println(BinSearch(s));

con.close();

}

}

Python implementation

The my_bin_search function performs a binary search and returns the index of the last T character.

def my_bin_search(s):

l = 0; r = len(s)

while l < r:

mid = (l + r) // 2

if (s[mid] == 'T'): l = mid + 1

else: r = mid

return l - 1;

The main part of the program. Read the input string s.

s = input()

If the first character of the string is F, print -1.

if (s[0] == 'F'): print(-1)

Print the answer.

else: print(my_bin_search(s))

Python implementation – bisect

import bisect

Read the input string s.

s = input()

If the first character of the string is F, print -1.

if s[0] == 'F':

print(-1)

Otherwise, compute and print the result.

else:

Invert the string. Now the letters are arranged in lexicographic order (‘F’ < ‘T’). Using binary search, find the position (index) of the first ‘T’ (the index of the ‘T’ that immediately follows an ‘F’).

index = bisect.bisect_right(s[::-1], 'F')

Recompute the index. Determine the position of the last ‘T’ in the original string.

index = len(s) - index – 1

Print the answer.

print(index)